package week_1.homework;

import java.sql.SQLOutput;

public class IntergerLinkedlistExample1 {
    public static void main(String[] args) {
        //（1）通过键盘输入一些整数，建立一个链表
        IntegerLinkedlist num1 = new IntegerLinkedlist(80);
        IntegerLinkedlist num2 = new IntegerLinkedlist(23);
        IntegerLinkedlist num3 = new IntegerLinkedlist(3);
        IntegerLinkedlist num4 = new IntegerLinkedlist(45);
        IntegerLinkedlist num5 = new IntegerLinkedlist(6);
        IntegerLinkedlist num6 = new IntegerLinkedlist(19);

        IntegerLinkedlist Head = num1;
        InsertNode(Head, num2);
        InsertNode(Head, num3);
        InsertNode(Head, num4);
        InsertNode(Head, num5);
        InsertNode(Head, num6);

        System.out.println("用户输入的整数链表：");
        PrintLinkedlist(Head);
        System.out.println();
        System.out.println("用选择排序法排序：");
        selectionSort(Head);
//        bubbleSort(Head);
        PrintLinkedlist(Head);
        System.out.println();
        System.out.println("删掉链表尾部结点后：");
        Deletenode(Head,num6);
        PrintLinkedlist(Head);
        System.out.println();
        System.out.println("将删掉的结点插入到链表头：");
        InsertNode1(Head,num6);
        PrintLinkedlist(Head);
    }

    //（2）实现节点插入、删除、输出等操作
    //链表的输出方法。
    public static void PrintLinkedlist(IntegerLinkedlist Head) {
        IntegerLinkedlist node = Head;//链表的头不能动。
        while (node != null) {
            System.out.print(" " + node.number);
            node = node.next;
        }
    }

    //头插法的方法。
    public static void InsertNode1(IntegerLinkedlist Head, IntegerLinkedlist node) {
        node.next = Head;
        Head = node;
        System.out.print("" + Head.number);
    }

    //尾插法的方法。
    public static void InsertNode(IntegerLinkedlist Head, IntegerLinkedlist node) {
        IntegerLinkedlist temp = Head;
        //遍历链表，找到链表末尾。
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    //链表的中间插入。
    public static void InsertNode(IntegerLinkedlist Head, IntegerLinkedlist node1, IntegerLinkedlist node2) {
        IntegerLinkedlist point = Head;
        while ((point.number != node1.number) & point != null) {
            point = point.next;
        }
        if (point.number == node1.number) {
            node1.next = point.next;
            point.next = node2;
        }
    }

    //链表的删除方法。
    public static void Deletenode(IntegerLinkedlist Head, IntegerLinkedlist node) {//这里的node要指向需要删除对象的前一个节点。
        IntegerLinkedlist prenode = Head, currentnode = Head;
        while (prenode != null) {
            if (currentnode != node) {
                prenode = currentnode;
                currentnode = currentnode.next;
            } else {
                break;
            }
        }
        prenode.next = currentnode.next;
    }

    //使用冒泡排序法或者选择排序法根据数值大小对链表进行排序。
    //链表的选择排序法。
     public static IntegerLinkedlist selectionSort(IntegerLinkedlist Head) {
         //记录每次循环的最小值
         int temp ;
         IntegerLinkedlist curNode = Head;
         while (curNode != null) {
             /**
              * 内重循环从当前节点的下一个节点循环到尾节点，
              * 找到和外重循环的值比较最小的那个，然后与外重循环进行交换
              */
             IntegerLinkedlist nextNode = curNode.next;
             while (nextNode != null) {
                 //比外重循环的小值放到前面
                 if (nextNode.number < curNode.number) {
                     temp = nextNode.number;
                     nextNode.number = curNode.number;
                     curNode.number = temp;
                 }
                 nextNode = nextNode.next;
             }
             curNode = curNode.next;
         }
         return Head;
     }

    //链表的冒泡排序法。
    public static IntegerLinkedlist bubbleSort(IntegerLinkedlist Head){
        if(Head == null || Head.next == null)  //链表为空或者仅有单个结点
            return Head;
        IntegerLinkedlist cur = null, tail = null;
        cur = Head;

        while(cur.next != tail){
            while(cur.next != tail){
                if(cur.number > cur.next.number){
                    int temp = cur.number;
                    cur.number = cur.next.number;
                    cur.next.number = temp;
                }
                cur = cur.next;
            }

            tail = cur;  //下一次遍历的尾结点是当前结点
            cur = Head;     //遍历起始结点重置为头结点
        }

        return Head;
    }
}


